package bst;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author yuh
 * @Date Created in 上午8:28 2018/4/13
 * @Description
 */
public class BSTDemo {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    static int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }

    static void reverseTree(TreeNode root) {
        if (root == null) {
            return;
        }
        swap(root);
        reverseTree(root.left);
        reverseTree(root.right);
    }

    /**
     * 包含node的有没有
     * @param node
     * @param sum
     * @return
     */
    static boolean pathSum(TreeNode node, int sum) {
        if (node == null) {
            return false;
        }
        if (node.left == null && node.right == null) {
            return node.val == sum;
        }
        return pathSum(node.left, sum - node.val)
                || pathSum(node.right, sum - node.val);
    }

    //几条路径就看有几个叶子节点
    static List<String> getAllPath(TreeNode node) {
        List<String> vectors = new ArrayList<>();
        if (node == null) {
            return vectors;
        }
        if (node.left == null && node.right == null) {
            vectors.add(String.valueOf(node.val));
            return vectors;
        }


        //如果有子树
        List<String> pathL = getAllPath(node.left);
        for (String s : pathL) {
            vectors.add(String.format("%d->%s", node.val, s));
        }
        List<String> pathR = getAllPath(node.right);
        for (String s : pathR) {
            vectors.add(String.format("%d->%s", node.val, s));
        }

        return vectors;
    }

    static int pathSumIII(TreeNode node, int sum) {
        if (node == null) {
            return 0;
        }
        //遍历每一个节点
        int res = 0;
        res = findPath(node, sum);
        res += pathSumIII(node.left, sum);
        res += pathSumIII(node.right, sum);
        return res;
    }

    /**
     * 从一个节点开始 有几条路径
     * @param node
     * @param sum
     * @return
     */
    private static int findPath(TreeNode node, int sum) {
        if(node == null){
            return 0;
        }
        int res = 0;
        if(node.val == sum){
            res += 1;
        }
        res += findPath(node.left,sum-node.val);
        res += findPath(node.right,sum-node.val);
        return res;
    }

    /**
     * 寻找最近的父节点
     * @param root
     * @param node1
     * @param node2
     * @return
     */
    static TreeNode lowestCommonAncestor(TreeNode root,TreeNode node1,TreeNode node2){
        if(root == null){
            return null;
        }
        //先判断两个节点的具体位置 如果在同一面就一直往下走
        if(node1.val > root.val && node2.val > root.val){
            return lowestCommonAncestor(root.right,node1,node2);
        }

        if(node1.val < root.val && node2.val < root.val){
            return lowestCommonAncestor(root.left,node1,node2);
        }

        //上述条件全都不满足 那么还有三种情况 全都直接返回即可
        //      root                node1       node2
        //node1      node2          node2       node1
        return root;

    }


    static void swap(TreeNode node) {
        TreeNode tmp = node.left;
        node.left = node.right;
        node.right = tmp;
    }

    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(1, new TreeNode(2, new TreeNode(4, null, null), null), new TreeNode(3, new TreeNode(6, new TreeNode(7, null, null), null), new TreeNode(5, null, null)));
        //System.out.println(maxDepth(treeNode));
        //reverseTree(treeNode);
        //System.out.println();
        //System.out.println(pathSum(treeNode, 2));
        //System.out.println(getAllPath(treeNode));
        System.out.println(pathSumIII(treeNode,6));
    }
}
